import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> list =new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        for(int i=0;(i<nums.length-2)||nums[i]<=0;i++){
            int left=i+1;
            int right=nums.length-1;
           fun(left,right,-nums[i],nums);
           while((i<nums.length-2)||(nums[i]<=0&&nums[i+1]==nums[i]){
            i++;
           }
        }
        return list;
    }
public void fun(int left,int right,int val,int[] nums){ 
    while(left<right){
         List<Integer> arr=new ArrayList<>();
        int leftVal=nums[left];
        int rightVal=nums[right];
        if(leftVal+rightVal>val){
           while(left<right&&nums[right]==rightVal){
            right--;
           }
        }else if(leftVal+rightVal<val){
           while(left<right&&nums[left]==leftVal){
            left++;
           }
        }else{
          arr.add(nums[left]);
          arr.add(nums[right]);
          arr.add(-val);
          list.add(arr);
          while(left<right&&nums[right]==rightVal){
            right--;
            
           }
           while(left<right&&nums[left]==leftVal){
            left++;
           }
        }

    }

}



    }
